package com.love.labuladong.unionlist;

/**
 * @Author : zh
 * @Description : 并查集
 * @Date : 2024-09-24 13:13
 */
public class UnionFindList {

    public static int MANX = 1000001;

    // 每个集合往上的指针
    public int[] father = new int[MANX];
    //每个集合的大小
    public int[] size = new int[MANX];
    // 栈
    public int[] stack = new int[MANX];

    public int n;


    public UnionFindList(int n){
        this.n = n;
    }

    public UnionFindList build(){
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
        return this;
    }


    // i 节点，往上一直找，找到代表节点返回
    public int find(int i){
        // 沿途收集了几个点
        int size = 0;
        // i == father[i] : i 作为该集合的代表元素
        // 如果i不是代表节点，就让它往上找代表节点
        while (i != father[i]){
            stack[size++] = i;
            // 上一跳
            i = father[i];
        }
        // 沿途节点收集好了，i已经跳到代表节点了
        while (size > 0){
            father[stack[--size]] = i;
        }

        return i;
    }


    /**
     * 查x所在的集合，和y所在的结合是否为一个集合
     * @param x
     * @param y
     * @return
     */
    public boolean isSameSet(int x,int y){
        //代表节点一样，那就是一个集合
        return find(x) == find(y);
    }


    /**
     * 把 x 所在集合和 y 所在集合，合并成一个集合
     * @param x
     * @param y
     */
    public UnionFindList union(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            // fx代表 ： 大小
            // fy代表 ： 大小
            // 大集合吸收小集合
            if(size[fx] >= size[fy]){
                size[fx] += size[fy];
                father[fy] = fx;
            }else {
                size[fy] += size[fy];
                father[fx] = fy;
            }
        }
        return this;
    }


    public static void main(String[] args) {
        UnionFindList un = new UnionFindList(20).build();
        un.union(2,5)
                .union(3,21)
                .union(5,9);

        boolean sameSet = un.isSameSet(2, 9);
        System.out.println(sameSet);

    }


}
